package org.xingole.leetcode.das.monostack;

import java.util.Arrays;

/**
 * Problem Description:
 * <a href="https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/">
 * Shortest Unsorted Continuous Subarray
 * </a>
 */
public class ShortestUnsortedContinuousSubarray {

     public int findUnsortedSubarray(int[] nums) {
          return 0;
     }

     /**
      * <a href="https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/solutions/911677/zui-duan-wu-xu-lian-xu-zi-shu-zu-by-leet-yhlf/">
      * Solution One - Sorting
      * </a>
      */
     public int findUnsortedSubarrayWithSorting( int[] nums ) {
          if ( isSorted(nums) ) {
               return 0;
          }

          int[] numsSorted = new int[nums.length];
          System.arraycopy(nums, 0, numsSorted, 0, nums.length);
          Arrays.sort(numsSorted);

          int left = 0;
          while (nums[left] == numsSorted[left]) {
               left++;
          }
          int right = nums.length - 1;
          while (nums[right] == numsSorted[right]) {
               right--;
          }

          return right - left + 1;
     }

     private boolean isSorted(int[] nums) {
          for ( int i = 1; i < nums.length; i++ ) {
               if (nums[i] < nums[i-1]) {
                    return false;
               }
          }

          return true;
     }

     // using the math property.
     public int findUnsortedSubarrayWithoutExtraSpace(int[] nums) {
          int n = nums.length;
          int maxn = Integer.MIN_VALUE, right = -1;
          int minn = Integer.MAX_VALUE, left  = n;

          // Assume that nums[n...+infinity] = +infinity and nums[-infinity, -1] = -infinity.
          // Loop invariant: minn is the minimum number in [n - i, +infinity] and 
          // numsA is contained in the [0..left-1] range.
          for ( int i = 0; i < n; i++ ) {
               if ( maxn > nums[i] ) {
                    right = i;
               } else {
                    maxn = nums[i];
               }

               if ( minn < nums[n - i - 1]) {
                    left = n - i - 1;
               } else {
                    minn = nums[n - i - 1];
               }
          }

          return right == -1 ? 0 : right - left + 1;
     }



}
